package 链表;

import java.util.*;

/**
 * @Author zxl
 * @Date 2021/12/19 22:24
 * @Desc
 */
public class 合并链表 {

    public static List<Node> initData() {
        Node node1 = new Node();
        node1.value = 1;
        Node node2 = new Node();
        node2.value = 2;
        Node node3 = new Node();
        node3.value = 3;
        Node node4 = new Node();
        node4.value = 10;

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        Node node11 = new Node();
        node11.value = 2;
        Node node12 = new Node();
        node12.value = 5;
        Node node13 = new Node();
        node13.value = 7;
        Node node14 = new Node();
        node14.value = 9;

        node11.next = node12;
        node12.next = node13;
        node13.next = node14;

        List<Node> list = new ArrayList<>();

        list.add(node1);
        list.add(node11);
        return list;
    }

    /**
     * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
     *
     * @param args
     */
    public static void main(String[] args) {

        List<Node> list = initData();
        Node head1 = list.get(0);
        Node head2 = list.get(1);
        System.out.println("合并前，链表1：" + head1.toString());
        System.out.println("合并前，链表2：" + head2.toString());
//        Node mergeNode = mergeNodeList(head1,head2);
        Node mergeNode = mergeNodeList2(head1, head2);
//        List<Node> nodeList = new ArrayList<>();
//        nodeList.add(head1);
//        nodeList.add(head2);
//        Node mergeNode = mergeNodeList(nodeList);
        System.out.println("合并过后，链表：" + mergeNode.toString());

    }

    public static Node mergeNodeList2(Node head1, Node head2) {
        Node newHead = new Node();
        Node headTemp = newHead;
        Node temp1 = head1;
        Node temp2 = head2;
        while (temp1 != null || temp2 != null) {
            if (temp1 == null && temp2 != null) {
                newHead.next = temp2;
                newHead = newHead.next;
                temp2 = temp2.next;
            } else if (temp2 == null && temp1 != null) {
                newHead.next = temp1;
                newHead = newHead.next;
                temp1 = temp1.next;
            } else if (temp1.value < temp2.value) {
                newHead.next = temp1;
                newHead = newHead.next;
                temp1 = temp1.next;
            } else {
                newHead.next = temp2;
                newHead = newHead.next;
                temp2 = temp2.next;
            }
        }
        return headTemp.next;
    }


    /**
     * 合并多个
     *
     * @param linkList
     * @return
     */
    public static Node mergeNodeList(List<Node> linkList) {
        Node head = new Node();
        Node temp = head;
        head.value = -1;
        Queue<Node> queue = new PriorityQueue<>(linkList.size(), Comparator.comparingInt(a -> a.value));
        for (Node node : linkList) {
            if (node != null) {
                queue.add(node);
            }
        }
        while (!queue.isEmpty()) {
            Node min = queue.poll();
            temp.next = min;
            temp = temp.next;
            if (min.next != null) {
                queue.add(min.next);
            }
        }
        return head.next;
    }


    /**
     * 合并两个链表
     *
     * @param head1
     * @param head2
     * @return
     */
    public static Node mergeNodeList(Node head1, Node head2) {

        Node newHead = new Node();
        Node curr = newHead;
        while (head1 != null || head2 != null) {
            if (head1 == null) {
                curr.next = head2;
                curr = curr.next;
                head2 = head2.next;
            } else if (head2 == null) {
                curr.next = head1;
                curr = curr.next;
                head1 = head1.next;
            } else {
                if (head1.value < head2.value) {
                    curr.next = head1;
                    curr = curr.next;
                    head1 = head1.next;
                } else {
                    curr.next = head2;
                    curr = curr.next;
                    head2 = head2.next;
                }
            }

        }

        return newHead.next;

    }
}
